Hilbert Space Embeddings of Hidden Markov Models.
Hidden Markov Models (HMMs) are important tools for modeling sequence data. However, they are restricted to discrete latent states, and are largely restricted to Gaussian and discrete observations. And, learning algorithms for HMMs have predominantly relied on local search heuristics, with the exception of spectral methods such as those described below. We propose a nonparametric HMM that extends traditional HMMs to structured and non-Gaussian continuous distributions. Furthermore, we derive a localminimum-free kernel spectral algorithm for learning these HMMs. We apply our method to robot vision data, slot car inertial sensor data and audio event classification data, and show that in these applications, embedded HMMs exceed the previous state-of-the-art performance. 1.
Kernelized Sorting.
We propose an algorithm for permuting or sorting multiple  sets (or bags) of objects such that they can ultimately be represented ef-  ciently using kernel principal component analysis. This framework generalizes  sorting from scalars to arbitrary inputs since all computations  involve inner products which can be done in Hilbert space and kernelized.
Discriminative frequent subgraph mining with optimality guarantees.

Hilbert space embeddings of conditional distributions with applications to dynamical systems.
In this paper, we extend the Hilbert space embedding approach to handle conditional distributions. We derive a kernel estimate for the conditional embedding, and show its connection to ordinary embeddings. Conditional embeddings largely extend our ability to manipulate distributions in Hibert spaces, and as an example, we derive a nonparametric method for modeling dynamical systems where the belief state of the system is maintained as a conditional embedding. Our method is very general in terms of both the domains and the types of distributions that it can handle, and we demonstrate the effectiveness of our method in various dynamical systems. We expect that conditional embeddings will have wider applications beyond modeling dynamical systems. 1.
Dynamic mixed membership blockmodel for evolving networks.
In a dynamic social or biological environment, interactions between the underlying actors can undergo large and systematic changes. Each actor can assume multiple roles and their degrees of affiliation to these roles can also exhibit rich temporal phenomena. We propose a state space mixed membership stochastic blockmodel which can track across time the evolving roles of the actors. We also derive an efficient variational inference procedure for our model, and apply it to the Enron email networks, and rewiring gene regulatory networks of yeast. In both cases, our model reveals interesting dynamical roles of the actors. 1.
Near%2Doptimal Supervised Feature Selection among Frequent Subgraphs.
Graph classification is an increasingly important step in numerous application domains, such as function prediction of molecules and proteins, computerised scene analysis, and anomaly detection in program flows. Among the various approaches proposed in the literature, graph classification based on frequent subgraphs is a popular branch: Graphs are represented as (usually binary) vectors, with components indicating whether a graph contains a particular subgraph that is frequent across the dataset. On large graphs, however, one faces the enormous problem that the number of these frequent subgraphs may grow exponentially with the size of the graphs, but only few of them possess enough discriminative power to make them
KELLER estimating time%2Dvarying interactions between genes.

Tailoring density estimation via reproducing kernel moment matching.
Moment matching is a popular means of parametric density estimation. We extend this technique to nonparametric estimation of mixture models. Our approach works by embedding distributions into a reproducing kernel Hilbert space, and performing moment matching in that space. This allows us to tailor density estimators to a function class of interest (i.e., for which we would like to compute expectations). We show our density estimation approach is useful in applications such as message compression in graphical models, and image classification and retrieval. 1.
Kernelized Sorting.
We propose an algorithm for permuting or sorting multiple  sets (or bags) of objects such that they can ultimately be represented ef-  ciently using kernel principal component analysis. This framework generalizes  sorting from scalars to arbitrary inputs since all computations  involve inner products which can be done in Hilbert space and kernelized.
Kernel Measures of Independence for non%2Diid Data.
Many machine learning algorithms can be formulated in the framework of statistical independence such as the Hilbert Schmidt Independence Criterion. In this paper, we extend this criterion to deal with structured and interdependent observations. This is achieved by modeling the structures using undirected graphical models and comparing the Hilbert space embeddings of distributions. We apply this new criterion to independent component analysis and sequence clustering. 1
A Hilbert Space Embedding for Distributions.
Abstract. We describe a technique for comparing distributions without the need for density estimation as an intermediate step. Our approach relies on mapping the distributions into a reproducing kernel Hilbert space. Applications of this technique can be found in two-sample tests, which are used for determining whether two sets of observations arise from the same distribution, covariate shift correction, local learning, measures of independence, and density estimation. Kernel methods are widely used in supervised learning [1, 2, 3, 4], however they are much less established in the areas of testing, estimation, and analysis of probability distributions, where information theoretic approaches [5, 6] have long been dominant. Recent examples include [7] in the context of construction of graphical models, [8] in the context of feature extraction, and [9] in the context of independent component analysis. These methods have by and large a common issue: to compute quantities such as the mutual information, entropy, or Kullback-Leibler divergence, we require sophisticated space partitioning and/or
A Hilbert Space Embedding for Distributions.
Abstract. We describe a technique for comparing distributions without the need for density estimation as an intermediate step. Our approach relies on mapping the distributions into a reproducing kernel Hilbert space. Applications of this technique can be found in two-sample tests, which are used for determining whether two sets of observations arise from the same distribution, covariate shift correction, local learning, measures of independence, and density estimation. Kernel methods are widely used in supervised learning [1, 2, 3, 4], however they are much less established in the areas of testing, estimation, and analysis of probability distributions, where information theoretic approaches [5, 6] have long been dominant. Recent examples include [7] in the context of construction of graphical models, [8] in the context of feature extraction, and [9] in the context of independent component analysis. These methods have by and large a common issue: to compute quantities such as the mutual information, entropy, or Kullback-Leibler divergence, we require sophisticated space partitioning and/or
A dependence maximization view of clustering.
We propose a family of clustering algorithms based on the maximization of dependence between the input variables and their cluster labels, as expressed by the Hilbert-Schmidt Independence Criterion (HSIC). Under this framework, we unify the geometric, spectral, and statistical dependence views of clustering, and subsume many existing algorithms as special cases (e.g. k-means and spectral clustering). Distinctive to our framework is that kernels can also be applied on the labels, which can endow them with particular structures. We also obtain a perturbation bound on the change in k-means clustering. 1
Supervised feature selection via dependence estimation.
We introduce a framework for filtering features that employs the Hilbert-Schmidt Independence Criterion (HSIC) as a measure of dependence between the features and the labels. The key idea is that good features should maximise such dependence. Feature selection for various supervised learning problems (including classification and regression) is unified under this framework, and the solutions can be approximated using a backward-elimination algorithm. We demonstrate the usefulness of our method on both artificial and real world datasets. 1
Study on the Vision Reading Algorithm based on Template Matching and Neural Network.

Gene selection via the BAHSIC family of algorithms.
Motivation Identifying significant genes among thousands of sequences on a microarray is a central challenge for cancer research in bioinformatics. The ultimate goal is to detect the genes that are involved in disease outbreak and progression. A multitude of methods have been proposed for this task of feature selection, yet the selected gene lists differ greatly between different methods. To accomplish biologically meaningful gene selection from microarray data, we have to understand the theoretical connections and the differences between these methods. In this article, we define a kernel-based framework for feature selection based on the Hilbert-Schmidt Independence Criterion and backward elimination, called BAHSIC. We show that several well-known feature selectors are instances of BAHSIC, thereby clarifying their relationship. Furthermore, by choosing a different kernel, BAHSIC allows us to easily define novel feature selection algorithms. As a further advantage, feature selection via BAHSIC works directly on multiclass problems. Results In a broad experimental evaluation, the members of the BAHSIC family reach high levels of accuracy and robustness when compared to other feature selection techniques. Experiments show that features selected with a linear kernel provide the best classification performance in general, but if strong non-linearities are present in the data then nonlinear kernels can be more suitable. Availability: Accompanying homepage is
A Kernel Statistical Test of Independence.
Although kernel measures of independence have been widely applied in machine learning (notably in kernel ICA), there is as yet no method to determine whether they have detected statistically significant dependence. We provide a novel test of the independence hypothesis for one particular kernel independence measure, the Hilbert-Schmidt independence criterion (HSIC). The resulting test costs O(m 2), where m is the sample size. We demonstrate that this test outperforms established contingency table and functional correlation-based tests, and that this advantage is greater for multivariate data. Finally, we show the HSIC test also applies to text (and to structured data more generally), for which no other independence test presently exists. 1
Colored Maximum Variance Unfolding.
Maximum variance unfolding (MVU) is an effective heuristic for dimensionality reduction. It produces a low-dimensional representation of the data by maximizing the variance of their embeddings while preserving the local distances of the original data. We show that MVU also optimizes a statistical dependence measure which aims to retain the identity of individual observations under the distancepreserving constraints. This general view allows us to design “colored ” variants of MVU, which produce low-dimensional representations for a given task, e.g. subject to class labels or other side information. 1
Colored Maximum Variance Unfolding.
Maximum variance unfolding (MVU) is an effective heuristic for dimensionality reduction. It produces a low-dimensional representation of the data by maximizing the variance of their embeddings while preserving the local distances of the original data. We show that MVU also optimizes a statistical dependence measure which aims to retain the identity of individual observations under the distancepreserving constraints. This general view allows us to design “colored ” variants of MVU, which produce low-dimensional representations for a given task, e.g. subject to class labels or other side information. 1
Supervised Feature Selection via Dependence Estimation
We introduce a framework for filtering features that employs the Hilbert-Schmidt Independence Criterion (HSIC) as a measure of dependence between the features and the labels. The key idea is that good features should maximise such dependence. Feature selection for various supervised learning problems (including classification and regression) is unified under this framework, and the solutions can be approximated using a backward-elimination algorithm. We demonstrate the usefulness of our method on both artificial and real world datasets. 1
Classifying EEG for brain%2Dcomputer interfaces learning optimal filters for dynamical system features.

Crossing Minimization Problems of Drawing Bipartite Graphs in Two Clusters.
The crossing minimization problem is a classic and very important problem in graph drawing (Pach, Toth 1997); the results directly a#ect the e#ectiveness of the layout, especially for very large scale graphs. But in many cases crossings cannot be avoided. In this paper we present two models for bipartite graph drawing, aiming to reduce crossings that cannot be avoided in the traditional bilayer drawings. We characterize crossing minimization problems in these models, and prove that they are  NP-complete.
Real%2Dtime 3D Finger Pointing for an Augmented Desk.
The augmented desk is gaining popularity in recent HCI research. Its layout of a large horizontal screen on the desk enhances immersive and intense collaborative experiences. A responsive and unimpeded input interface is important for an efficient interaction in such an environment. In this paper, we developed a real-time stereo vision-based finger pointing interface for our augmented desk that supports drag-and-drop operation by the tap-and-move of the index finger. The core of our system is a 3D fingertip tracking system, which requires both careful calibration and efficient fingertip localization algorithm. To meet these requirements, we have designed a two-step calibration method that strikes a good balance between accuracy and convenience. Furthermore, based on the chain code representation of the contour, we propose the direction cancellation vector as a tool for fingertip localization. Our algorithm works efficiently with a time complexity of O (n) in term of the length of the chain code. Currently our system allows a user to select and move the displayed contents on the screen directly using his fingertip, and it is applied to the interactive graph drawing paradigm proposed by do Nascimento and Eades (2001). In this application, our real-time pointing interface enables the user to interact with a graph drawing program dynamically, which results in optimal layouts of graphs with maximum symmetry. In the last section, the strength and weakness of our system are discussed, and further suggestions to improve the system are also given..
Visualisation and Analysis of Large and Complex Scale%2Dfree Networks.
Scale-free networks appear in many application domains such as social and biological networks [BA99, BB03, BO04]. Roughly speaking, scale-free networks have power-law degree distribution, ultra-short average path length and high clustering coefficient [BA99, BB03, BO04]. This paper presents new methods for visualising scale-free networks in three dimensions. To make effective use of the third dimension and minimise occlusion, we produce graph visulaisations with nodes constrained to lie on parallel planes or on the surface of spheres. We implement the algorithms using a variation of a fast force-directed graph layout method [QE00]. Results with real world data sets such as IEEE InfoVis citation and collaboration networks and a protein-protein interaction network show that our method can be useful for visual analysis of large and complex scale-free networks. We also discuss the issue of visualisation of evolving networks and network integration. 1.
Visualisation and Analysis of Network Motifs.
Many of the complex networks that occur both in nature and in technology are built up from frequently recurring patterns of basic structural elements. These structural patterns known as motifs play a significant role in the function of the network. Visualisation is a useful tool for understanding the structure in a network. The quality of a visualisation can be significantly improved if it effectively displays these motifs. In this paper we present visualisations designed to highlight motifs detected through analysis. We argue that these visualisations designed to show functionally important subgraphs give a greater insight into the function of the network. 1.
Phase Synchrony Rate for the Recognition of Motor Imagery in Brain%2DComputer Interface.

WilmaScope Graph Visualisation.
Our visualisation of the IEEE InfoVis citation network is based on 3D graph visualisation techniques. To make effective use of the third dimension we use a layered approach, constraining nodes to lie on parallel planes depending on parameters such as year of publication or link degree. Within the parallel planes nodes are arranged using a fast force-directed layout method. A number of clusters representing different research areas were identified using a self organising map approach. Keywords: map infovis contest, graph visualization, self organizing 1
